package sort.advanced_sort;

import java.util.Arrays;

public class Demo6_HeapSort_Up {
    /**
     * 堆排序的算法步骤：
     *      1. 把无序数组构建成二叉堆。升序排列则构建成最大堆，降序排列则构建成最小堆。
     *      2. 循环删除堆顶元素（不是完全从内存中删除，只是和数组末尾节点交换位置），替换到二叉堆的末尾，调整替换后堆顶成为新的堆（最大/最小）
     *
     *  以下代码为堆排序的升序（构建最大堆）
     */
    /**
     * 最大堆的"下沉"调整
     */
    public static void downAdjust(int[] arr, int parentIndex, int size) {
        //（左）孩子节点位置
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < size) {
            //如果有右孩子，并且右孩子更大，选右孩子
            if (childIndex + 1 < size && arr[childIndex + 1] > arr[childIndex]) {
                childIndex++;
            }
            if (arr[parentIndex] >= arr[childIndex]) {
                break;
            }
            //交换
            swap(arr, parentIndex, childIndex);
            parentIndex = childIndex;
            childIndex = parentIndex * 2 + 1;
        }
    }

    public static void heapSort(int[] arr) {
        //1.将无序数组构建成最大堆，构建堆的本质是让"所有非叶子节点"做"下沉"操作。
        int len = arr.length;
        for (int i = len / 2 - 1; i >=0; i--){
            downAdjust(arr, i, len);
        }
//        System.out.println(Arrays.toString(arr));
        //2. 循环删除堆顶元素，移动到数组末尾，调整堆为新的最大堆
        for (int i = len - 1; i > 0; i--){
            //最后1个元素和第1个元素进行交换
            swap(arr, i, 0);
            //3. 调整从新的最大堆
            downAdjust(arr,0,i);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            heapSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        heapSort(arr);
        printArray(arr);
    }
}
